public class Test {


    //给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。
    // 如果两个链表不存在相交节点，返回 null 。
    //https://leetcode.cn/problems/intersection-of-two-linked-lists/description/
    public static  MySingleList.ListNode getIntersectionNode(MySingleList.ListNode headA, MySingleList.ListNode headB) {
        MySingleList.ListNode pl = headA;//假设长的链表为headA
        MySingleList.ListNode ps = headB;//假设短的链表为headB
        //1.先求两个链表的长度
        int lenA = 0;
        int lenB = 0;
        while (pl != null) {
            lenA++;
            pl = pl.next;
        }
        while (ps != null) {
            lenB++;
            ps = ps.next;
        }


        //求完长度让pl 和 ps重新指向头节点
        pl = headA;
        ps = headB;

        //2.求两个链表的长度差
        int len = lenA - lenB;
        if (len < 0) {
            pl = headB;//长的链表
            ps = headA;//短的链表
            len = lenB - lenA;//将len改为正数

        }

        //走完上述两步，pl一定指向最长的链表，ps一定指向最短的链表
        //3.操作pl和ps就行
        //让最长的链表走len步
        while (len != 0) {
            pl = pl.next;
            len--;
        }
        //4.pl和ps同时走，直到他们相遇
        while (pl != ps) {
            pl = pl.next;
            ps = ps.next;
        }
        if (pl == null) {
            return null;//没有相交
        }
        return pl;
    }

    public  static  void createCut(MySingleList.ListNode headA, MySingleList.ListNode headB){
        headB.next.next.next= headA.next.next;
    }

    public static void main3(String[] args) {
        MySingleList mySingleList1 = new MySingleList();
        mySingleList1.addLast(1);
        mySingleList1.addLast(2);
        mySingleList1.addLast(11111);
        mySingleList1.addLast(4);
        mySingleList1.addLast(5);
        MySingleList mySingleList2 = new MySingleList();
        mySingleList2.addLast(33);
        mySingleList2.addLast(22);
        mySingleList2.addLast(311);
        createCut(mySingleList1.head,mySingleList2.head);
        MySingleList.ListNode ret = getIntersectionNode(mySingleList1.head,mySingleList2.head);
        System.out.println(ret.val);
    }
        //将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
    public static MySingleList.ListNode mergeTwoLists(MySingleList.ListNode headA, MySingleList.ListNode headB) {
        MySingleList.ListNode newhead = new MySingleList.ListNode(-1);
        MySingleList.ListNode tmp = newhead;
        //遍历这两个列表
        while(headA != null && headB != null ){
            if(headA.val < headB.val){
                tmp.next = headA;
                headA = headA.next;
                tmp = tmp.next;
            }else{
                tmp.next = headB;
                headB = headB.next;
                tmp = tmp.next;
            }
        }
        if(headA!= null){
            tmp.next = headA;
        }
        if(headB!= null){
            tmp.next = headB;
        }
        return newhead.next;
    }


    public static void main2(String[] args) {
        MySingleList mySingleList1 = new MySingleList();
        mySingleList1.addLast(1);
        mySingleList1.addLast(2);
        mySingleList1.addLast(3);
        mySingleList1.addLast(4);
        mySingleList1.addLast(5);
        MySingleList mySingleList2 = new MySingleList();
        mySingleList2.addLast(33);
        mySingleList2.addLast(22);
        mySingleList2.addLast(311);
        mySingleList2.addLast(42);
        mySingleList2.addLast(51);
        MySingleList.ListNode    newhead  =  mergeTwoLists(mySingleList1.head,mySingleList2.head);
        mySingleList2.display2(newhead);
    }





    public static void main1(String[] args) {
        MySingleList mySingleList = new MySingleList();
       /* mySingleList.createList();
        mySingleList.display();

        System.out.println();
        int ret = mySingleList.size();
        System.out.println(ret);*/


        mySingleList.addFist(1);
        mySingleList.addFist(2);
        mySingleList.addFist(3);
        mySingleList.addFist(4);
        mySingleList.addFist(5);
        mySingleList.display();
        System.out.println();

        mySingleList.addLast(100);
        mySingleList.display();

        System.out.println();
        System.out.println(mySingleList.contains(11111));

        System.out.println();



        mySingleList.addIndex(3,11);
        mySingleList.addIndex(0,69);
        mySingleList.addIndex(8,22);
        mySingleList.display();


        System.out.println();
        mySingleList.remove(22);
        mySingleList.display();
        System.out.println();
        mySingleList.remove(69);
        mySingleList.display();
        System.out.println();
        mySingleList.remove(100);
        mySingleList.display();

        System.out.println();
        /*System.out.println("===================");
        mySingleList.clear();
        mySingleList.display();*/


        System.out.println();

        System.out.println("============================");
        mySingleList.reverseList();
        mySingleList.display();
        System.out.println();
        MySingleList.ListNode ret =  mySingleList.reverseList();
        mySingleList.display2(ret);


        System.out.println();
        System.out.println("===========================");
        MySingleList.ListNode  k = mySingleList.middleNode();
        System.out.println(k.val);
    }

    public static void main(String[] args) {
        MySingleList mySingleList1 = new MySingleList();
        mySingleList1.addLast(1);
        mySingleList1.addLast(2);
        mySingleList1.addLast(3);
        mySingleList1.addLast(4);
        mySingleList1.addLast(5);

        mySingleList1.createLoop();
        System.out.println(mySingleList1.hasCycle());

        MySingleList.ListNode a = mySingleList1.detectCycle();
        System.out.println(a.val);


    }
}
